package org.czx.datactruct.second;

import org.czx.datactruct.first.BagInterface;

import java.util.Arrays;

/**
 * @author czx
 * @date 2020/8/21 9:00
 */
public class ResizableArrayBag<T> implements BagInterface<T> {
    private static final int DEFAULT_CAPACITY = 25;
    private static final int MAX_CAPACITY = 10000;
    private T[] bag;

    private int numberOfEntries;

    private boolean initialized = false;

    public ResizableArrayBag() {
        this(DEFAULT_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public ResizableArrayBag(int capacity) {
        checkCapacity(capacity);
        bag = (T[]) new Object[capacity];
        numberOfEntries = 0;
        initialized = true;
    }

    @Override
    public int getCurrentSize() {
        return numberOfEntries;
    }

    @Override
    public boolean isEmpty() {
        return numberOfEntries == 0;
    }

    @Override
    public boolean add(T newEntry) {
        checkInitialization();
        if (isArrayFull()) {
            doubleCapacity();
        }
        bag[numberOfEntries++] = newEntry;
        return true;
    }

    @Override
    public T remove() {
        checkInitialization();
        T result = null;
        if(this.numberOfEntries > 0) {
            result = this.bag[numberOfEntries-1];
            this.bag[numberOfEntries-1] = null;
            numberOfEntries--;
        }
        return result;
    }

    @Override
    public boolean remove(T anEntry) {
        checkInitialization();
        int index = indexOf(anEntry);
        T result = removeEntry(index);
        return anEntry.equals(result);
    }

    @Override
    public void clear() {
        checkInitialization();
        while(!isEmpty())
            remove();
    }

    @Override
    public int getFrequencyOf(T anEntry) {
        checkInitialization();
        int count = 0;
        int index = 0;
        while(index < numberOfEntries) {
            if(anEntry.equals(this.bag[index]))
                count++;
            index++;
        }
        return count;
    }

    @Override
    public boolean contains(T anEntry) {
        checkInitialization();
        return indexOf(anEntry)!=-1;
    }

    @Override
    public T[] toArray() {
        checkInitialization();
        @SuppressWarnings("unchecked")
        T[] temp = (T[]) new Object[numberOfEntries];
        for(int i=0;i<numberOfEntries;i++) {
            temp[i] = this.bag[i];
        }
        return temp;
    }

    /**
     * 扩容两倍
     */
    private void doubleCapacity() {
        int newLength = bag.length << 1;
        checkCapacity(newLength);
        bag = Arrays.copyOf(bag, newLength);
    }

    private boolean isArrayFull() {
        return numberOfEntries >= bag.length;
    }

    private void checkCapacity(int capacity) {
        if (capacity > MAX_CAPACITY)
            throw new IllegalArgumentException("Attempt to create a bag whose capacity exceeds allowed maximum max_capacity");
    }

    public void checkInitialization() {
        if(!initialized)
            throw new SecurityException("Array bag is not initialized properly");
    }
    /**
     * 找到返回index，找不到返回-1
     * @param anEntry
     * @return
     */
    public int indexOf(T anEntry) {
        int index = 0;
        int result = -1;
        boolean found = false;
        while(!found && index < numberOfEntries) {
            if(anEntry.equals(this.bag[numberOfEntries])) {
                result = index;
                found = true;
            }
            index++;
        }
        return result;
    }
    public T removeEntry(int index) {
        T result = null;
        if(!isEmpty() && index>0) {
            result = this.bag[index];
            this.bag[index] =  this.bag[numberOfEntries-1];
            this.bag[numberOfEntries-1] = null;
            numberOfEntries--;
        }
        return result;
    }
}
